#ifndef WORKERTREE
#define WORKERTREE

/*!
 * \file WorkerTree.h
 * \author aimery aviles / thomas raynal
 * \version 2.0
 */

#include <vector>
#include <iostream>
#include <stack>
#include <set>
#include "AbstractGridSlaveTask.h"
#include "AbstractTask.h"
#include "Worker.h"
#include "Utils.h"

#define UNDEFINED -1

/*! \namespace Network
 * 
 * Group master/slave task template & task handling utilities (trees & graphs)
 */
namespace MasterWorkerFramework
{

/*! \class Worker
* \brief  Represent a tree of slave tasks
*/
class WorkerTree
{
public:

	WorkerTree()
	{
		index__=0;
		size_=0;
	}

	/*!
	*  \brief Resolve a worker
	*
	*/
	void ResolveNode (int position)
	{
		nodes.at(position-1)->Resolve();
		size_++;
	}


private:
	std::vector<AbstractGridSlaveTask*> trees;
	std::vector<Worker*> nodes;
	int size_;
	int index__;
	friend class WorkerGraph;
	friend class WorkTable;

	
	void BuildTree (std::vector<AbstractGridSlaveTask*> tasks)
	{
		bool bottom= false;
		AbstractGridSlaveTask* current;
		std::vector<std::string*> elts;
		std::stack<std::string*> stck;
		

		for (int i=0; i<tasks.size();i++)
		{
			Worker* node = new Worker(tasks.at(i));
			nodes.push_back(node);
		}

		for (int i=0; i<tasks.size();i++)
		{
			current = tasks.at(i);
			bottom= false;
			elts.clear();
			stck.push (current->GetHash());

			while (bottom==false)
				{
					if (current->GetParent()==NULL)
					{
						bottom=true;
					}
					else
					{
						if (!(std::find(elts.begin(), elts.end(),current->GetParent()->GetHash()) != elts.end()))
						{
							elts.push_back(current->GetParent()->GetHash());
							stck.push (current->GetParent()->GetHash());
							current = current->GetParent();
						}
						else
						{
							bottom=true;
						}
					}
				}

				while (!stck.empty())
					{
						Worker* n =Get(stck.top());
						stck.pop();

						if (stck.size()==0)
						{
							break;
						}
						else
						{
							n->AddEdge(Get(stck.top()));
						}
					}
		}

		Reduce();
	}

	Worker* Get (std::string* hash)
	{
			for (std::vector<Worker*>::iterator worker = nodes.begin(); worker != nodes.end(); worker++)
			{
				if ((*worker)->id_==hash)
				{
					return *worker;
				}
			}
	}



	static	bool SortFct(Worker* n1, Worker* n2)
	{
		return (n1->index_ < n2->index_);
	}

	void Reduce()
	{

		for (std::vector<Worker*>::iterator worker = nodes.begin(); worker != nodes.end(); worker++)
		{
			if ((*worker)->index_== UNDEFINED)
			{
				Eval (*worker);
			}
		}

			
		for (std::vector<Worker*>::iterator worker = nodes.begin(); worker != nodes.end(); worker++)
		{
			if ((*worker)->index_== UNDEFINED)
			{
				(*worker)->index_=index__;
				break;
			}

		}

		sort (nodes.begin(), nodes.end(), SortFct); 
	}

		void Eval (Worker* n)
		{
				std::stack<Worker*> stck;
				std::set<Worker*> elts_done;

				for (std::vector<Worker*>::iterator worker = n->edges_->begin(); worker != n->edges_->end(); worker++)
				{
					if ((*worker)->index_== UNDEFINED)
					{
						Eval (*worker);
						(*worker)->link_ = min(n->link_,(*worker)->link_);
						(*worker)->index_ = index__;
						index__++;
						elts_done.insert((*worker));
						stck.push((*worker));
					}
					
					else if (elts_done.end()!=elts_done.find(*worker))
					{
						n->link_ = min(n->link_,(*worker)->link_);
					}
				}

				if (n->index_ ==n->link_)
				{
					Worker* n1 = stck.top();
					stck.pop();

					while (!(*n1==*n))
					{
							Worker* n1 = stck.top();
							stck.pop();
					}
				}

		}

};

}
#endif
